计算几何

将几何问题转化为计算机可处理的数据结构与算法，以高效解决点集关系、空间划分、路径规划等实际需求。

---

1. 基本问题与算法

• 凸包（Convex Hull）
  从一堆散乱的点中找出最小“橡皮筋”包围的多边形。
  常见算法：

  • Graham 扫描
  • Andrew 算法
  • 时间复杂度：$O(n \log n)$

• 最近点对（Closest Pair）
  在平面上找距离最短的两点。
  经典做法：分治法（Divide and Conquer）。
  时间复杂度：$O(n \log n)$

• Voronoi 图 & Delaunay 三角剖分

  • Voronoi 图：将平面划分为若干凸多边形，各多边形内任意点到该多边形关联点的距离最近。
  • Delaunay 三角剖分：与 Voronoi 图互为对偶，常用于网格生成。
  • 应用：GIS、计算机图形学、最近邻搜索等。

---

2. 数据结构

• KD 树（k-d Tree）

  • 适合多维空间中点的查找与范围查询。
  • 平均构建与查询复杂度：$O(n \log n)$（视平衡程度而定）。

• 线段树 / 扫描线（Segment Tree / Sweep Line）

  • 线段树：动态更新与查询线段计数、覆盖长度等。
  • 扫描线：沿某一轴“扫”过去，实时维护活动线段集合，用于求解线段交点、面积并等问题。

---

3. 应用场景

1. 计算机图形学

   • 碰撞检测
   • 可视域剖分（Visibility Partitioning）
   • 网格生成与蒙皮（Meshing / Skinning）

2. 机器人与自动驾驶

   • 路径规划（A* 的几何扩展、Dijkstra + 可视图）
   • 避障算法（基于 Voronoi、RRT、PRM 等）

3. 地理信息系统（GIS）

   • 地形建模
   • 最短路径与网络分析
   • 空间邻域查询与缓冲区分析

---

4. 注意事项

• 数值鲁棒性

  • 浮点误差会导致几何判定错误（点在线上、交点判断）。
  • 可采用：
    • 增加容差（epsilon）
    • 使用整数 / 分数 / 任意精度算术库

• 维度扩展

  • 二维算法往往可以推广到三维或更高维，但时间／空间复杂度急剧增长。
  • 三维凸包、三维最近点对等问题实现难度与运算量都显著提升，需要在效率与可实现性之间权衡。

---

总结：
计算几何不仅是“把几何丢给计算机算”，更需在数据结构、数值稳定性、算法设计三者之间找到平衡，才能让几何问题在实际工程中快速、可靠地运行。